
//主要负责合并数组
function merge(leftArr,rightArr){
    //创建结果数组
    let result=[]
    let leftIndex=0
    let rightIndex=0
    while(leftIndex < leftArr.length && rightIndex < rightArr.length){
        if(leftArr[leftIndex]<=rightArr[rightIndex]){
            result.push(leftArr[leftIndex])
            leftIndex++
        }
        else{
            result.push(rightArr[rightIndex])
            rightIndex++
        }
    }
    //将剩余元素放入
    if(leftIndex<leftArr.length){
       result=result.concat(leftArr.slice(leftIndex))
    }
    if(rightIndex<rightArr.length){
        result=result.concat(rightArr.slice(rightIndex))
    }
    return result
}
//主要负责拆解数组
function MergeSort(arr) {
    if(arr.length<2){
        //数组不可再分
        return arr
    }
    let mid=Math.floor(arr.length/2)
    //将数组分为左右两个数组，调用自身进行继续划分
    const left=MergeSort(arr.slice(0,mid))
    const right=MergeSort(arr.slice(mid))
    //合并数组
    return merge(left,right)
}


// 测试函数
function testInsertionSort() {
    let arr = [];
    for (let i = 0; i < 10; i++) {
        arr.push(Math.floor(Math.random() * 100));
    }
    
    console.log("排序前:", arr);
    arr=MergeSort(arr);
    console.log("排序后:", arr);
    
    // 验证排序结果
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            console.log("排序失败!");
            return;
        }
    }
    console.log("排序成功!");
}

// 运行测试
testInsertionSort();